package Demo1_29;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-29
 * Time:19:29
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    // 构造函数，用于初始化节点的值
    TreeNode(int x) {
        val = x;
    }
}

public class SameTree {
    // 判断两棵二叉树是否相同的方法
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如果两个节点都为空，认为这部分结构相同
        if (p == null && q == null) {
            return true;
        }
        // 如果一个节点为空，另一个不为空，结构不同
        if (p == null || q == null) {
            return false;
        }
        // 如果对应节点的值不相等，两棵树不同
        if (p.val != q.val) {
            return false;
        }
        // 递归比较左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main(String[] args) {
        // 创建第一棵二叉树
        TreeNode tree1 = new TreeNode(1);
        tree1.left = new TreeNode(2);
        tree1.right = new TreeNode(3);

        // 创建第二棵二叉树
        TreeNode tree2 = new TreeNode(1);
        tree2.left = new TreeNode(2);
        tree2.right = new TreeNode(3);

        // 创建 SameTree 类的实例
        SameTree solution = new SameTree();
        // 调用 isSameTree 方法判断两棵树是否相同
        boolean result = solution.isSameTree(tree1, tree2);
        System.out.println("两棵树是否相同: " + result);

        // 创建第三棵二叉树，与第一棵树不同
        TreeNode tree3 = new TreeNode(1);
        tree3.left = new TreeNode(2);

        // 再次调用 isSameTree 方法判断第一棵树和第三棵树是否相同
        result = solution.isSameTree(tree1, tree3);
        System.out.println("两棵树是否相同: " + result);
    }
}
